#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#define FOR(i,a,n) for(int i=a;i<int(n);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

const int mod = 1000000009;
class DSU
{
    static const int MAXN = 100100;
    int *father;
    public:
    DSU(int n = 0)
    {
        father = new int[n];
        REP(i,n) father[i] = i;
    }
    int getGroup(int x)
    {
        if(father[x]!=x) father[x] = getGroup(father[x]);
        return father[x];
    }
    bool merge(int a,int b)
    {
        int x = getGroup(a);
        int y = getGroup(b);
        if(x==y) return false;
        else
        {
            father[x] = y;
            return true;
        }
    }
};
int main()
{
    int n,m;
    int ans = 1;
    cin>>n>>m;
    DSU dsu(n+10);
    REP(i,m)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(!dsu.merge(a,b)) ans = ans*2%mod;
        printf("%d\n",ans-1);
    }
	return 0;
}
